// https://leetcode.cn/problems/ones-and-zeroes/description/

// 算法思路总结：
// 1. 动态规划解决二维费用的0-1背包问题
// 2. 状态定义：dp[j][k]表示使用j个0和k个1能构造的最大子集大小
// 3. 每个字符串消耗zeroNums个0和oneNums个1
// 4. 倒序遍历避免重复选择同一字符串（0-1背包）
// 5. 三重循环：物品→0的容量→1的容量
// 6. 时间复杂度：O(len×m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int findMaxForm(vector<string>& strs, int m, int n) 
    {
        int len = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (int i = 1 ; i <= len ; i++)
        {
            for (int j = m ; j >= 0 ; j--)
            {
                for (int k = n ; k >= 0 ; k--)
                {
                    string& str = strs[i - 1];
                    int zeroNums = 0, oneNums = 0;
                    for (const char& ch : str)
                    {
                        if (ch == '0')
                            zeroNums++;
                        else 
                            oneNums++;
                    }

                    if (j - zeroNums >= 0 && k - oneNums >= 0)
                    {
                        dp[j][k] = max(dp[j][k], dp[j - zeroNums][k - oneNums] + 1);
                    }
                }
            }
        }

        return dp[m][n];
    }
};

int main()
{
    vector<string> strs1 = {"10", "0001", "111001", "1", "0"};
    vector<string> strs2 = {"10", "0", "1"};

    int m1 = 5, m2 = 1;
    int n1 = 3, n2 = 1;

    Solution sol;

    cout << sol.findMaxForm(strs1, m1, n1) << endl;
    cout << sol.findMaxForm(strs2, m2, n2) << endl;

    return 0;
}